Wormhole: A Fast Ordered Index for In-memory Data Management (EuroySys'19)

As an example, in a B+ tree of one million keys a lookup requires about 20 key comparisons on average. When the B+ tree grows to billions of keys, which is not rare with small KV items managed in today’s large memory of hundreds of GBs, on average 30 or more key-comparisons are required for a lookup. Lookup in both examples can be an order of magnitude slower than that in hash tables.